package com.zufe.khw;

public class Test2 {
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5};
        quickSort(arr, 0, arr.length - 1);
        for (int j : arr) {
            System.out.print(j + " ");
        }
    }
    public static void quickSort(int[] arr, int low, int high) {
        if(low >= high) {
            return;
        }
        //定义基准值为数组的第一个元素
        int start = low + 1;
        int end = high;
        while(start < end){
            //从右向左找到第一个小于基准值的元素
            while(start < end && arr[end] >= arr[low]){
                end--;
            }
            //从左向右找到第一个大于基准值的元素
            while(start < end && arr[start] <= arr[low]){
                start++;
            }
            //交换两个元素
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        //基准值复位
        int temp = arr[start];
        arr[start] = arr[low];
        arr[low] = temp;
        //递归左边
        quickSort(arr, low, start - 1);
        //递归右边
        quickSort(arr, start + 1, high);
    }
}
